package org.hmh.offer;

import org.hmh.leetcode.dataStruct.TreeNode;
import org.hmh.util.TreeUtil;

/**
 * Definition for binary tree
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
public class t4 {
    public static class Solution {
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            return construct(pre, in, 0, pre.length, 0);
        }

        public TreeNode construct(int[] pre, int[] in, int start, int end, int index) {
            if (start > end || index >= pre.length) {
                return null;
            }
            TreeNode root = new TreeNode(pre[index]);
            int split = start;
            while (pre[index] != in[split]) {
                split++;
            }
            root.left = construct(pre, in, start, split - 1, index + 1);
            root.right = construct(pre, in, split + 1, end, index + (split + 1 - start));
            return root;
        }
    }

    public static void main(String[] args) {
        int[] pre = {1, 2, 3, 4, 5, 6, 7};
        int[] in = {3, 2, 4, 1, 6, 5, 7};

        Solution solution = new Solution();
        TreeNode treeNode = solution.reConstructBinaryTree(pre, in);
        TreeUtil.print(treeNode);
    }


}